// KMP
#include "../constant.h"
#include "./strpos.h"

int Strpos(char str[], char pattern[]);
void getNext(char pattern[], int next[]);
void printNext(char pattern[], int next[]);

// KMP Core
int Strpos(char str[], char pattern[])
{
    int strLen = StrLen(str);
    int patternLen = StrLen(pattern);
    int *next = (int *)malloc(sizeof(int) * patternLen);
    getNext(pattern, next);
    int j = 0, i = 0;
    while (j < patternLen && i < strLen)
    {
        if (j == 0 || pattern[j] == str[i])
        {
            // j退到0时，需要让i、j向前移动，从而促使子串向前移动
            // 因为j退到0时，即使此时仍不匹配，也无法回退，此时只能促进字串前进
            j++;
            i++;
        }
        else
        {
            j = next[j - 1];
        }
    }
    if (j >= patternLen)
    {
        return i - patternLen;
    }
    else
    {
        return -1;
    }
}

void getNext(char pattern[], int next[])
{
    int n = StrLen(pattern);
    next[0] = 0;
    int j = 0;
    int i = 1;
    while (i < n)
    {
        if (j == 0 || pattern[j] == pattern[i])
        {
            // 如果说j为0那么有两种情况
            // (1) j为初始值0时
            // 此时对于长度仅为2的字符串时，无论其是否存在公共前后缀，其next[i]=1恒成立
            // (2) j是通过回溯最终到达0的，也就是说直到回溯到最初的字符之前，字符串无公共前后缀
            // 此时next[i] = j+1，j、i向前移动
            next[i] = j + 1;
            j++;
            i++;
        }
        else
        {
            // 回溯j
            j = next[j - 1];
        }
    }
    printf("[KMP Core]\n");
    printNext(pattern, next);
}

void printNext(char pattern[], int next[])
{
    int n = StrLen(pattern);
    printf("next: \n");
    for (int i = 0; i < n; i++)
    {
        printf("%c ", pattern[i]);
    }
    printf("\n");
    for (int i = 0; i < n; i++)
    {
        printf("%d ", next[i]);
    }
    printf("\n");
}
